性质

树的基本概念与遍历

常见遍历方式：

  • 前序遍历：根 -> 左 -> 右
  • 中序遍历：左 -> 根 -> 右
  • 后序遍历：左 -> 右 -> 根
  • 层序遍历：从上到下、从左到右一层一层遍历（借助队列）

基本概念：

性质/概念 简述
树的高度 / 深度 根到最远叶子的路径长度
叶子节点个数 没有任何孩子的节点数
节点总数 = 内部 + 叶子 总节点 = 内部节点数 + 叶子节点数
二叉树的性质 n个节点的二叉树，最多有n-1条边；满二叉树节点数是奇数等
递归与DFS/BFS在树中的应用 先根、后根等都可以用递归实现；层序使用BFS实现
线索二叉树、并查集树等 数据结构优化的变种

常见树的类型与特点

类型 特点 示例
普通二叉树 每个节点最多两个孩子 无特殊结构限制
完全二叉树 每层节点都尽量往左填满，最后一层从左到右连续 堆结构就是典型
满二叉树 每个节点要么是叶子节点，要么恰好有两个孩子 节点数 = 2^h - 1
完美二叉树 满二叉树 + 最后一层也是满的 理想结构，如满堆
二叉搜索树（BST） 中序遍历是有序的 左<根<右
AVL树（平衡BST） 任一节点左右子树高度差不超过1 高效搜索结构
红黑树 特殊BST，带颜色信息控制平衡，插入删除更高效 STL中map/set底层实现
堆（大根堆/小根堆） 完全二叉树 + 父子有序性（大于/小于） 优先队列
霍夫曼树 带权路径最短的树，常用于压缩编码 Huffman编码
线段树 / 树状数组 用于区间查询、更新问题 竞赛常用数据结构

遍历能否唯一确定一棵树？

给定哪些遍历？ 能否唯一构造树？
中序 + 前序 ✅ 唯一
中序 + 后序 ✅ 唯一
前序 + 后序 ❌ 不唯一（除非是满二叉树）
单独给中序 / 前序 / 后序 ❌ 都不唯一
单独给层序 ❌ 不唯一
完全二叉树 + 任意遍历 ✅ 可以唯一确定（结构固定）

⬅️ 二叉树 🏠 00-天梯赛 ➡️ L2-007 家庭房产